from collections import deque
from typing import List


class AC:

    def __init__(self, words: List[str]):
        '''
        假设是26个小写字母, @see c13_trie/trie_2.py     以数组形式创建前缀树
        '''
        # 总共的单词
        self.n = n = len(words)
        # 边的个数为   所有字符
        # 节点的个数为 所有字符 + root节点
        self.total = total = sum(len(word) for word in words) + 1

        # 前缀树 + direct_table直通表（优化AC自动机，使fail指针不绕圈直指）
        self.trie = [[0] * 26 for _ in range(total)]
        # 每个单词结尾的节点的编号
        self.end = [0] * n
        # 树上节点的fail指针
        self.fail = [0] * total
        # fail指针的反向建图[多叉树结构](连通表建图)
        self.inverse_fail_tree = [[] for _ in range(total)]
        # 节点的编号(树的size)
        self.cnt = 0
        self.build(words)

    def build(self, words: List[str]):
        # 构建前缀树，顺便填充end表
        for i, word in enumerate(words):
            self._insert(i, word)
        # print("打印前缀树:")
        # print(*self.trie, sep='\n')
        # print("每个单词的end节点:")
        # print(self.end, sep='\n')

        # 构建fail指针，和直通表
        self._set_fail()
        # print("打印直通表:")
        # print(*self.trie, sep='\n')
        # print("打印fail指针表:")
        # print(self.fail, sep='\n')

        # 直接预处理出来，反向fail树
        self._build_inverse_fail_tree()
        # print(*self.inverse_fail_tree,sep='\n')

    def _insert(self, i, word: str):
        # @see c13_trie/trie_2.py     以数组形式创建前缀树
        trie = self.trie
        cur = 0

        for char in word:
            path = ord(char) - ord('a')
            if not trie[cur][path]:
                self.cnt += 1
                trie[cur][path] = self.cnt
            cur = trie[cur][path]
        self.end[i] = cur  # 每个单词结尾的节点的编号

    def _set_fail(self):
        # 生成好前缀树后，设置fail指针
        # AC自动机优化 将前缀树+直通表，(柔和在一起，当然也可以分开创建一个，保留原来的前缀树)
        # bfs 遍历前缀树 设置fail指针和直通表
        #   1) 如果u有去向下级节点v的路 =》 设置下级节点v的fail指针，fail[v_id] = fail[u]走向v字符的路
        #   2) 如果没有 =》 设置我u到下级节点v的直通表，table[u_id][v] = fail[u]走向v的路
        # 默认，根节点，以及所有第一层节点的fail指针都指向根节点0
        trie, fail = self.trie, self.fail
        q = deque([v for v in trie[0] if v])
        while q:
            for _ in range(len(q)):
                u = q.popleft()
                for v in range(26):
                    if trie[u][v]:
                        q.append(trie[u][v])
                        fail[trie[u][v]] = trie[fail[u]][v]
                    else:
                        trie[u][v] = trie[fail[u]][v]

    def _build_inverse_fail_tree(self):
        inverse_fail_tree, fail = self.inverse_fail_tree, self.fail
        for u, v in enumerate(fail):
            inverse_fail_tree[v].append(u)  # 反向建fail树
        inverse_fail_tree[0].remove(0)

    def match(self, article: str) -> List[int]:
        n, total, trie, inverse_fail_tree, end = self.n, self.total, self.trie, self.inverse_fail_tree, self.end
        times = [0] * total

        # 读入文章统计词频,这里的词频是，fail节点是没有统计到的
        u = 0
        for c in article:
            v = trie[u][ord(c) - ord('a')]
            times[v] += 1
            u = v
        # dfs 遍历 反向fail树， 完善词频
        def dfs(u):
            time = times[u]
            for v in inverse_fail_tree[u]:
                time += dfs(v)
            times[u] = time
            return time
        # 因为这个前缀树有可能层级太深，所以使用栈来实现
        # 第一次访问把孩子压栈，第二次访问则孩子已经处理完毕则出栈并统计词频
        def dfs2(u):
            stack = [u]
            visited = [False] * total
            while stack:
                u = stack[-1]
                if not visited[u]:
                    visited[u] = True
                    for v in inverse_fail_tree[u]:
                        stack.append(v)
                else:
                    stack.pop()
                    time = times[u]
                    for v in inverse_fail_tree[u]:
                        time += times[v]
                    times[u] = time

        dfs2(0)
        res = [0] * n
        for i, node in enumerate(end):
            res[i] = times[node]
        return res



# words = ['abca', 'bcb', 'ca', 'cc', 'd']
words = ['abcd', 'bc', 'c']
article = 'abcdbcc'
ac = AC(words)
ans = ac.match(article)
print(ans)
